
On souhaite montrer comment utiliser le principe du « diviser pour régner » afin de développer un produit de petits polynômes avec un minimum d'opérations de multiplication entre termes.
Pour cela, on va d'abord décrire cette méthode à l'aide d'un exemple simple de multiplication de nombre entiers, puis de petits polynômes, pour ensuite l'implémenter en Python.
II. Principe du « diviser pour régner »
Une multiplication entre deux nombres entiers nécessite de multiplier chaque chiffre du multiplicateur par chaque chiffre du multiplicande.
Si ces deux nombres ont n chiffres, cela exige n2 produits. La multiplication 10*10 nécessite ainsi 4 multiplications de chiffre.
On dit que le calcul a une complexité en temps quadratique, ou en O(n2).
Si on prend maintenant le produit de nombres entiers :
p = 10 × 10 × 11 × 11 × 12 × 12 × 13 × 13
En effectuant les calculs de gauche à droite, on obtient successivement :
p = (10×10) × 11 × 11 × 12 × 12 × 13 × 13
La 1re multiplication nécessite donc 4 opérations de multiplication entre chiffres.
En poursuivant les calculs :
p = 100 × 11 × 11 × 12 × 12 × 13 × 13
p = (100 × 11) × 11 × 12 × 12 × 13 × 13
On a ainsi besoin jusque là de 4 + 6 opérations de multiplication.
Puis :
p = (1100 × 11) × 12 × 12 × 13 × 13
Ce qui fait alors au total 4 + 6 + 8 opérations.
etc..
En poursuivant les calculs vers la droite, on obtient finalement 4 + 6 + 8 + 10 + 12 + 14 + 16 = 70 opérations de multiplication en tout pour ce produit.
Considérons maintenant le même produit réarrangé :
p = ((10 × 10) × (11 × 11)) × ((12 × 12) × (13 × 13))
Si on effectue les calculs en respectant la règle de priorité des parenthèses, on peut alors les représenter sur un arbre de produits :
On a donc besoin dans ce cas de seulement 59 opérations de multiplication entre chiffres au lieu de 70 précédemment.
Il s'agit du principe du « diviser pour régner » :
- Diviser : découper un problème initial en sous-problèmes ;
- Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ;
- Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.
On peut également appliquer ce même principe pour la multiplication de petits polynômes :
Important : L'intérêt principal des arbres de produits est en fait de tirer parti des algorithmes de multiplication rapide d'entiers ou de polynômes.
La situation la plus simple est celle où l'on cherche à calculer le produit d'un grand nombre de « petits » entiers ou polynômes.
Dans ce contexte, et pourvu que l'on dispose d'une multiplication rapide, l'algorithme diviser pour régner est plus efficace que la méthode classique.
Dans notre cas, on va déjà montrer ses avantages dans le développement d'un produit de petits polynômes sans parler de multiplication rapide.
III. Implémenter le développement d'un produit de polynômes
On utilise à nouveau notre classe Polynome à laquelle on ajoute un attribut permettant de compter le nombre d'opérations de multiplication entre termes nécessaires pour développer un produit de polynômes :
Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Polynome: def __init__(self, liste_coefs=[0]): # méthode constructeur de la classe # on définit la liste des coefficients du polynôme [a0, a1, ..., an] self.coefs = liste_coefs # on initialise le nombre d'opérations de multiplication entre termes self.nombre_operations = 0 # suppression si nécessaire des zéros en queue de liste de coefficients. Exemple : [2, 3, 1, 0, 0] -> [2, 3, 1] self.reduire() ... |
Le code de la méthode permettant de multiplier deux polynômes devient alors :
Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Polynome: ... def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 polynômes : (1 + x) * (1 + 2x) = 1 + 3x + 2x^2 # initialisation de la liste des coefficients qu'avec des zéros liste_coefs=[0]*(len(self.coefs)+len(other.coefs)-1) # exemple : [0, 0, 0] for i1 in range(len(self.coefs)): # parcours des indices des coefs du polynôme n°1 for i2 in range(len(other.coefs)): # parcours des indices des coefs du polynôme n°2 # multiplication des coefficients d'indices i1 et i2 liste_coefs[i1+i2] = liste_coefs[i1+i2] + self.coefs[i1]*other.coefs[i2] poly = Polynome(liste_coefs) # création de l'objet Polynome basé sur la liste # ajout du nombre d'opérations de multiplication entre termes effectuées lors de la multiplication entre polynômes poly.compteur_operations = self.compteur_operations + other.compteur_operations + len(self.coefs)*len(other.coefs) return poly # renvoie le polynôme résultat de la multiplication |
Rappel important : les objets Polynome de notre classe sont représentés par une liste de coefficients dont la longueur est égale au degré du polynôme + 1 :
Par exemple, le polynôme X3 + 2 = 2 + 0.X + 0.X2 + X3 sera représenté par la liste de coefficients [2, 0, 0, 1].
Par conséquent, le développement du produit (X3 + 2)(X3 + 2) nécessite en fait 4*4 = 16 multiplications entre termes.
III-A. Méthode classique
Testons maintenant l'opérateur de multiplication entre polynômes avec la méthode classique :
Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 | # création des polynômes p1 = X + 1; p2 = X + 2; p3 = X + 3; p4 = X + 4 p1 = Polynome([1,1]); p2 = Polynome([2,1]); p3 = Polynome([3,1]); p4 = Polynome([4,1]) # produit de polynômes p = p1*p1*p2*p2*p3*p3*p4*p4 print("produit = ({0})*({0})*({1})*({1})*({2})*({2})*({3})*({3})".format(p1,p2,p3,p4)) print() print("produit développé = " + str(p)) print() print("nombre d'opérations = " + str(p.nombre_operations)) |
Le code affiche :
produit = (1 + X)*(1 + X)*(2 + X)*(2 + X)*(3 + X)*(3 + X)*(4 + X)*(4 + X)
produit développé = 576 + 2400.X + 4180.X^2 + 3980.X^3 + 2273.X^4 + 800.X^5 + 170.X^6 + 20.X^7 + X^8
nombre d'opérations = 70
III-B. Principe du « diviser pour régner »
On peut également, comme on l'a vu précédemment, regrouper les sous-produits sur un arbre de produits.
On obtient ainsi la fonction récursive basée sur le principe du « diviser pour régner » :
Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 | def produit_polynomes(*polynomes): # test si le tuple polynomes contient plus de 1 élément if len(polynomes)>1: i=len(polynomes)//2 # valeur du milieu # appels récursifs return produit_polynomes(*polynomes[:i])*produit_polynomes(*polynomes[i:]) else: # sinon # renvoie l'unique polynôme du tuple return polynomes[0] |
Libre à chacun ensuite d'optimiser ce code.
Testons notre fonction avec ces quelques lignes :
Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 | # création des polynômes p1 = X + 1; p2 = X + 2; p3 = X + 3; p4 = X + 4 p1 = Polynome([1,1]); p2 = Polynome([2,1]); p3 = Polynome([3,1]); p4 = Polynome([4,1]) # p = ((p1*p1)*(p2*p2))*((p3*p3)*(p4*p4)) p = produit_polynomes(p1,p1,p2,p2,p3,p3,p4,p4) print("produit = ((({0})*({0}))*(({1})*({1})))*((({2})*({2}))*(({3})*({3})))".format(p1,p2,p3,p4)) print() print("produit développé = " + str(p)) print() print("nombre d'opérations = " + str(p.nombre_operations)) |
Le code affiche :
produit = (((1 + X)*(1 + X))*((2 + X)*(2 + X)))*(((3 + X)*(3 + X))*((4 + X)*(4 + X)))
produit développé = 576 + 2400.X + 4180.X^2 + 3980.X^3 + 2273.X^4 + 800.X^5 + 170.X^6 + 20.X^7 + X^8
nombre d'opérations = 59
IV. Module complet
On donne pour finir le contenu du module complet :
[CODE=Python]class Polynome:
def __init__(self, liste_coefs=[0]): # méthode constructeur de la classe
# on définit la liste des coefficients du polynôme [a0, a1, ..., an]
self.coefs = liste_coefs
# on initialise le nombre d'opérations de multiplication entre termes
self.nombre_operations = 0
# suppression si nécessaire des zéros en queue de liste de coefficients. Exemple : [2, 3, 1, 0, 0] -> [2, 3, 1]
self.reduire()
def __str__(self): # permet d'afficher le polynôme sous la forme 1 + 2x + 3x^2
s="" # initialisation de la chaîne de caractères
# on vérifie d’abord si le degré du polynôme est nul
if (len(self.coefs)-1==0):
return str(self.coefs[0])
else: # sinon
if self.coefs[0]!=0:
s=str(self.coefs[0]) + " + "
for i in range(1, len(self.coefs)): # parcours des indices des coefficients du polynôme : [a1, a2, ..., an]
if self.coefs[i]!=0: # si le coefficient de degré i n'est pas nul
if self.coefs[i]!=1: # si le coefficient de degré i est différent de 1
s+="{}.X^{} + ".format(self.coefs[i],i)
else: s+="X^{} + ".format(i)
# élimination des caractères en trop
s = s[:-3].replace("+ -", "- ").replace("X^1 ","X ").replace(" 1.X"," X")
if s[-2:]=="^1": s = s[:-2]
if s[:3]=="1.X": s = s[3:]
return s # on retourne l'expression du polynôme
def degre(self): # retourne le degré du polynôme
return (len(self.coefs)-1)
def __add__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2
# p1 = self, p2 = other
if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1
liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite.
else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ...
for i in range(n): # parcours des indices de liste_coefs
liste_coefs[i] = self.coefs[i] + other.coefs[i] # addition des coefficients de degré i
return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition
def __sub__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2
# p1 = self, p2 = other
if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1
liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite.
else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ...
for i in range(n): # parcours des indices de liste_coefs
liste_coefs[i] = self.coefs[i] - other.coefs[i] # addition des coefficients de degré i
return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition
def reduire(self):
# tant que le dernier élément de la liste est nul
while round(self.coefs[-1],12) == 0 and len(self.coefs)>1:
self.coefs.pop() # supprimer le dernier élément
for i in range(len(self.coefs)):
self.coefs[i] = round(self.coefs[i],12)
def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 polynômes : (1 + x) * (1 + 2x) = 1 + 3x + 2x^2
# initialisation de la liste des coefficients qu'avec des zéros
liste_coefs=[0]*(len(self.coefs)+len(other.coefs)-1) # exemple : [0, 0, 0]
for i1 in range(len(self.coefs)): # parcours des indices des coefs du polynôme n°1
for i2 in range(len(other.coefs)): # parcours des indices des coefs du polynôme n°2
# multiplication des coefficients d'indices i1 et i2
liste_coefs[i1+i2] = liste_coefs[i1+i2] + self.coefs[i1]*other.coefs[i2]
poly = Polynome(liste_coefs) # création de l'objet Polynome basé sur la liste
# ajout du nombre d'opérations de multiplication entre termes effectuées lors de la multiplication entre polynômes
poly.nombre_operations = self.nombre_operations + other.nombre_operations + len(self.coefs)*len(other.coefs)
return poly # renvoie le polynôme résultat de la multiplication
def __pow__(self, n): # méthode permettant de redéfinir l'opérateur de puissance : self ** n
# on crée l'objet poly à partir d'une liste contenant un seul élément 1, élément neutre pour la multiplication des polynômes
poly = Polynome([1])
for i in range(n): # on multiplie n fois poly par self à l'aide de[/1]...
La fin de cet article est réservée aux abonnés. Soutenez le Club Developpez.com en prenant un abonnement pour que nous puissions continuer à vous proposer des publications.